package com.gitee.ywj1352.算法.week06;

import com.gitee.ywj1352.算法.week02.TreeNode;

import java.util.LinkedList;

public class 二叉树的序列化与反序列化 {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    private void serializeHelper(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append("#").append(",");
            return;
        }
        sb.append(root.val).append(",");
        serializeHelper(root.left,sb);
        serializeHelper(root.right,sb);
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strArr = data.split("[,]");
        LinkedList<String> list = new LinkedList<String>();
        for(int i = 0 ; i < strArr.length;i ++){
            list.add(strArr[i]);
        }
        return  deserializeHelper(list);
    }

    public TreeNode deserializeHelper(LinkedList<String> list){
        if(list.size()==0){
            return null;
        }
        String preStr = list.removeFirst();
        TreeNode node;
        if(preStr.equals("#")){
            node = null;
            return node;
        } else {
            node = new TreeNode(Integer.valueOf(preStr));
        }
        TreeNode left = deserializeHelper(list);
        TreeNode right = deserializeHelper(list);
        node.left = left;
        node.right = right;
        return node;
    }

}
